home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-13 / tde3.zip / REGX.C < prev    next >
C/C++ Source or Header  |  1993-06-05  |  35KB  |  1,242 lines
  1. /*
  2.  * These functions compile a regular expression into an NFA and recognize
  3.  * a pattern.
  4.  *
  5.  * Regular expressions are often used to describe a pattern that might
  6.  * match several different or similar words.  An example of a regular
  7.  * expression subset is the wild card characters '*' and '?' used to list
  8.  * files in a directory.
  9.  *
  10.  * Might as well read the books and papers written by those who first wrote
  11.  * the various [a-z]?greps.  Ken Thompson was the author of grep.  In one
  12.  * weekend, Al Aho wrote egrep and fgrep.  Incidentally, when Dr. Aho was
  13.  * the guest speaker at the Distinguished Lecture Series at Georgia Tech,
  14.  * he personally autographed my copy of his book  _Compilers:  Principles,
  15.  * Techniques, and Tools_, aka the "Dragon Book."
  16.  *
  17.  * See:
  18.  *
  19.  *   Ken Thompson, "Regular Expression Search Algorithm."  _Communications
  20.  *      of the ACM_, 11 (No. 6): 419-422, 1968.
  21.  *
  22.  *   Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman, _Compilers: Principles,
  23.  *      Techniques, and Tools_, Addison-Wesley, Reading, Mass., 1986,
  24.  *      Chapter 3, "Lexical Analysis", pp 83-158.  ISBN 0-201-10088-6.
  25.  *
  26.  *   Robert Sedgewick, _Algorithms in C_, Addison-Wesley, Reading, Mass.,
  27.  *      1990, Chapter 20, "Pattern Matching", pp. 293-303, and Chapter 21,
  28.  *      "Parsing", pp. 305-317.  ISBN 0-201-51425-7.
  29.  *
  30.  *   Andrew Hume, "A Tale of Two Greps."  _Software--Practice and Experience_,
  31.  *      18 (No. 11): 1063-1072, 1988.
  32.  *
  33.  *
  34.  *                         Regular Expressions in TDE
  35.  *
  36.  * The core of the regular expression search algorithm in TDE is based on
  37.  * the nondeterministic finite-state machine in Dr. Segdewick's book.
  38.  * Additional parsing, operator precedence, and nfa construction and
  39.  * simulation info is from Dr. Aho's book.  The nfa node naming convention
  40.  * and additional nfa construction guidelines are from Ken Thompson's paper.
  41.  * I'm much too stupid to compile a regular expression into assembly language
  42.  * as suggested in Ken Thompson's paper, but I did get the idea to do the
  43.  * next best thing and added C library functions as NNODE terminal types.
  44.  *
  45.  * Searching for regular expressions in TDE is not very fast.  The worst
  46.  * case search, .*x, where x is any word or letter, is probably the slowest
  47.  * of any implementation with a regular expression search function.  However,
  48.  * TDE can handle a large regular expression subset.
  49.  *
  50.  *
  51.  * New editor name:  TDE, the Thomson-Davis Editor.
  52.  * Author:           Frank Davis
  53.  * Date:             June 5, 1991, version 1.0
  54.  * Date:             July 29, 1991, version 1.1
  55.  * Date:             October 5, 1991, version 1.2
  56.  * Date:             January 20, 1992, version 1.3
  57.  * Date:             February 17, 1992, version 1.4
  58.  * Date:             April 1, 1992, version 1.5
  59.  * Date:             June 5, 1992, version 2.0
  60.  * Date:             October 31, 1992, version 2.1
  61.  * Date:             April 1, 1993, version 2.2
  62.  * Date:             June 5, 1993, version 3.0
  63.  *
  64.  * This code is released into the public domain, Frank Davis.
  65.  * You may use and distribute it freely.
  66.  */
  67.  
  68. #include "tdestr.h"
  69. #include "common.h"
  70. #include "tdefunc.h"
  71. #include "define.h"
  72.  
  73.  
  74. /*
  75.  * types of nodes in the NFA.
  76.  *
  77.  * let's use the node naming convention in Ken Thompson's reg ex paper.
  78.  */
  79. #define CNODE           0
  80. #define NNODE           1
  81.  
  82. #define SCAN            -1
  83.  
  84. /*
  85.  * types of terminals in NNODEs.
  86.  *
  87.  * starting with simple ASCII terminals, it's easy to build in other types of
  88.  *  terminals, e.g. wild chars, BOL, EOL, and character classes.  actually,
  89.  *  we can easily build ANSI C ctype library function NNODEs.
  90.  */
  91. #define STRAIGHT_ASCII  0
  92. #define IGNORE_ASCII    1
  93. #define WILD            2
  94. #define BOL             3
  95. #define EOL             4
  96. #define CLASS           5
  97. #define NOTCLASS        6
  98. #define WHITESPACE      7
  99. #define ALPHA           8
  100. #define UPPER           9
  101. #define LOWER           10
  102. #define ALPHANUM        11
  103. #define DECIMAL         12
  104. #define HEX             13
  105.  
  106.  
  107. /*
  108.  * types of terminals in CNODEs.
  109.  */
  110. #define START           0
  111. #define ACCEPT          1
  112. #define OR_NODE         2
  113. #define JUXTA           3
  114. #define CLOSURE         4
  115. #define ZERO_OR_ONE     5
  116.  
  117.  
  118. int  lookahead;
  119. int  regx_rc;
  120. int  reg_len;
  121. int  parser_state;
  122. char class_bits[32];
  123. int  bit[8] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };
  124. int  c1;
  125. int  c2;
  126. int  ttype;
  127. int  regx_error_line;
  128.  
  129. NFA_TYPE  *nfa_pointer;
  130.  
  131. int  nfa_status;
  132. int  search_len;
  133. int  search_col;
  134. text_ptr search_string;
  135.  
  136. int  queued_states[REGX_SIZE+2];
  137. int  deque[REGX_SIZE*2];
  138. int  dq_head;
  139. int  dq_tail;
  140. int  stacked_node_count;
  141. int  reset_count;
  142.  
  143.  
  144. /*
  145.  * Name:    find_regx
  146.  * Purpose: To set up and find a regular expression.
  147.  * Date:    June 5, 1993
  148.  * Passed:  window:  pointer to current window
  149.  * Notes:   Keep the regular expression until changed.
  150.  */
  151. int  find_regx( WINDOW *window )
  152. {
  153. int  direction;
  154. int  new_string;
  155. char pattern[MAX_COLS];  /* text to be found */
  156. long found_line;
  157. long bin_offset;
  158. line_list_ptr ll;
  159. register WINDOW *win;  /* put window pointer in a register */
  160. int  rc;
  161. int  old_rcol;
  162. int  rcol;
  163.  
  164.    switch (g_status.command) {
  165.       case FindRegX :
  166.          new_string = TRUE;
  167.          direction  = FORWARD;
  168.          break;
  169.       case RepeatFindRegX :
  170.          new_string = FALSE;
  171.          direction  = FORWARD;
  172.          break;
  173.       case RepeatFindRegXBackward :
  174.          new_string = FALSE;
  175.          direction  = BACKWARD;
  176.          break;
  177.       default :
  178.          new_string = 0;
  179.          direction  = 0;
  180.          assert( FALSE );
  181.          break;
  182.    }
  183.  
  184.    win = window;
  185.    entab_linebuff( );
  186.    if (un_copy_line( win->ll, win, TRUE ) == ERROR)
  187.       return( ERROR );
  188.  
  189.    regx_error_line = win->bottom_line;
  190.  
  191.    /*
  192.     * get search text, using previous as default
  193.     */
  194.    rc = OK;
  195.    if (new_string == TRUE) {
  196.       *pattern = '\0';
  197.       if (regx.search_defined == OK) {
  198.  
  199.          assert( strlen( (char *)regx.pattern ) < MAX_COLS );
  200.  
  201.          strcpy( pattern, (char *)regx.pattern );
  202.       }
  203.  
  204.       /*
  205.        * string to find:
  206.        */
  207.       if (get_name( reg1, win->bottom_line, pattern,
  208.                     g_display.message_color ) != OK  ||  *pattern == '\0')
  209.          return( ERROR );
  210.       regx.search_defined = OK;
  211.  
  212.       assert( strlen( pattern ) < MAX_COLS );
  213.  
  214.       strcpy( (char *)regx.pattern, pattern );
  215.       rc = build_nfa( );
  216.       if (rc == ERROR)
  217.          regx.search_defined = ERROR;
  218.    }
  219.  
  220.    if (regx.search_defined == OK) {
  221.       old_rcol = win->rcol;
  222.       if (mode.inflate_tabs)
  223.          win->rcol = entab_adjust_rcol( win->ll->line, win->ll->len, win->rcol);
  224.       update_line( win );
  225.       show_search_message( SEARCHING, g_display.diag_color );
  226.       bin_offset = win->bin_offset;
  227.       if (direction == FORWARD) {
  228.          if ((ll = forward_regx_search( win, &found_line, &rcol )) != NULL) {
  229.             if (g_status.wrapped && g_status.macro_executing)
  230.                rc = ask_wrap_replace( win, &new_string );
  231.             if (rc == OK)
  232.                find_adjust( win, ll, found_line, rcol );
  233.             else
  234.                win->bin_offset = bin_offset;
  235.          }
  236.       } else {
  237.          if ((ll = backward_regx_search( win, &found_line, &rcol )) != NULL) {
  238.             if (g_status.wrapped && g_status.macro_executing)
  239.                rc = ask_wrap_replace( win, &new_string );
  240.             if (rc == OK)
  241.                find_adjust( win, ll, found_line, rcol );
  242.             else
  243.                win->bin_offset = bin_offset;
  244.          }
  245.       }
  246.       if (g_status.wrapped)
  247.          show_search_message( WRAPPED, g_display.diag_color );
  248.       else {
  249.          if (nfa_status == OK)
  250.             show_search_message( CLR_SEARCH, g_display.mode_color );
  251.          else
  252.             g_status.wrapped = TRUE;
  253.       }
  254.       if (ll == NULL) {
  255.          /*
  256.           * string not found
  257.           */
  258.          if (mode.inflate_tabs)
  259.             win->rcol = old_rcol;
  260.          combine_strings( pattern, find5a, (char *)regx.pattern, find5b );
  261.          error( WARNING, win->bottom_line, pattern );
  262.          rc = ERROR;
  263.       }
  264.       show_curl_line( win );
  265.       make_ruler( win );
  266.       show_ruler( win );
  267.    } else {
  268.       /*
  269.        * find pattern not defined
  270.        */
  271.       error( WARNING, win->bottom_line, find6 );
  272.       rc = ERROR;
  273.    }
  274.    return( rc );
  275. }
  276.  
  277.  
  278. /*
  279.  * Name:    forward_regx_search
  280.  * Purpose: search forward for regular expression
  281.  * Date:    June 5, 1993
  282.  * Passed:  window:  pointer to current window
  283.  *          rline:   pointer to real line counter
  284.  *          rcol:    pointer to real column variable
  285.  * Returns: position in file if found or NULL if not found
  286.  * Notes:   Start searching from cursor position to end of file.  If we hit
  287.  *           end of file without a match, start searching from the beginning
  288.  *           of file to cursor position.  (do wrapped searches)
  289.  */
  290. line_list_ptr forward_regx_search( WINDOW *window, long *rline, int *rcol )
  291. {
  292. register int len;
  293. int  i;
  294. int  end;
  295. register WINDOW *win;  /* put window pointer in a register */
  296. line_list_ptr ll;
  297.  
  298.    /*
  299.     * if cursor is beyond end of line then start at end of line
  300.     */
  301.    win  = window;
  302.    *rline = win->rline;
  303.    i = win->rcol + 1;
  304.    ll = win->ll;
  305.    len = ll->len;
  306.    if (i > len  &&  len != EOF) {
  307.       ll = ll->next;
  308.       ++*rline;
  309.       i = 0;
  310.    }
  311.    if (i < 0)
  312.       i = 0;
  313.  
  314.    *rcol = i;
  315.    ll = regx_search_forward( ll, rline, rcol );
  316.  
  317.    if (ll == NULL) {
  318.  
  319.       end = 0;
  320.       if (win->ll->next != NULL) {
  321.          end = win->ll->next->len;
  322.          win->ll->next->len = EOF;
  323.       }
  324.  
  325.       /*
  326.        * haven't found pattern yet - now search from beginning of file
  327.        */
  328.       g_status.wrapped = TRUE;
  329.  
  330.       *rcol = 0;
  331.       *rline = 1L;
  332.       ll = regx_search_forward( win->file_info->line_list, rline, rcol );
  333.  
  334.       if (ll == win->ll  &&  *rcol >= win->rcol)
  335.          ll = NULL;
  336.  
  337.       if (win->ll->next != NULL)
  338.          win->ll->next->len = end;
  339.    }
  340.    flush_keyboard( );
  341.  
  342.    if (ll != NULL)
  343.       bin_offset_adjust( win, *rline );
  344.    return( ll );
  345. }
  346.  
  347.  
  348. /*
  349.  * Name:    regx_search_forward
  350.  * Purpose: search forward for pattern using nfa
  351.  * Date:    June 5, 1993
  352.  * Passed:  ll:     pointer to current node in linked list
  353.  *          rline:  pointer to real line counter
  354.  *          col:    column in ll->line to begin search
  355.  * Returns: position in file if found or NULL if not found
  356.  * Notes:   run the nfa machine on each character in each line
  357.  */
  358. line_list_ptr regx_search_forward( line_list_ptr ll, long *rline, int  *col )
  359. {
  360.    if (ll->len == EOF)
  361.       return( NULL );
  362.    else {
  363.       switch (g_status.command) {
  364.          case DefineRegXGrep  :
  365.          case RepeatGrep :
  366.             nfa_pointer = &sas_nfa;
  367.             stacked_node_count = sas_regx.node_count;
  368.             break;
  369.          case FindRegX  :
  370.          case RepeatFindRegX :
  371.             nfa_pointer = &nfa;
  372.             stacked_node_count = regx.node_count;
  373.             break;
  374.          default :
  375.             assert( FALSE );
  376.             break;
  377.       }
  378.       nfa_status = OK;
  379.       search_string = ll->line;
  380.       search_len = ll->len;
  381.       search_col = *col;
  382.       reset_count = stacked_node_count * sizeof(int);
  383.       for (; !g_status.control_break;) {
  384.          for (; search_col <= search_len; search_col++) {
  385.             if (nfa_match( ) != ERROR) {
  386.                *col = search_col;
  387.                return( ll );
  388.             }
  389.          }
  390.          ++*rline;
  391.          ll = ll->next;
  392.          search_string = ll->line;
  393.          if (ll->len == EOF)
  394.             return( NULL );
  395.          search_len = ll->len;
  396.          search_col = 0;
  397.       }
  398.       return( NULL );
  399.    }
  400. }
  401.  
  402.  
  403. /*
  404.  * Name:    backward_regx_search
  405.  * Purpose: search backward for regular expression
  406.  * Date:    June 5, 1993
  407.  * Passed:  window:  pointer to current window
  408.  *          rline:   pointer to real line counter
  409.  *          rcol:    pointer to real column variable
  410.  * Returns: position in file if found or NULL if not found
  411.  * Notes:   Start searching from cursor position to end of file.  If we hit
  412.  *           end of file without a match, start searching from the beginning
  413.  *           of file to cursor position.  (do wrapped searches)
  414.  */
  415. line_list_ptr backward_regx_search( WINDOW *window, long *rline, int *rcol )
  416. {
  417. int  i;
  418. int  len;
  419. int  end;
  420. register WINDOW *win;  /* put window pointer in a register */
  421. line_list_ptr ll;
  422.  
  423.    win  = window;
  424.    *rline = win->rline;
  425.  
  426.    /*
  427.     * see if cursor is on EOF line.  if so, move search start to previous node.
  428.     */
  429.    if (win->ll->len != EOF) {
  430.       ll = win->ll;
  431.       i  = win->rcol - 1;
  432.       len = ll->len;
  433.       if (i >= len)
  434.          i = len - 1;
  435.    } else {
  436.       ll = win->ll->prev;
  437.       --*rline;
  438.       i = 0;
  439.       if (ll != NULL)
  440.          i = ll->len - 1;
  441.    }
  442.    *rcol = i;
  443.    ll = regx_search_backward( ll, rline, rcol );
  444.  
  445.    if (ll == NULL  &&  win->rline <= win->file_info->length) {
  446.  
  447.       end = 0;
  448.       if (win->ll->prev != NULL) {
  449.          end = win->ll->prev->len;
  450.          win->ll->prev->len = EOF;
  451.       }
  452.  
  453.       /*
  454.        * haven't found pattern yet - now search from end of file
  455.        */
  456.       g_status.wrapped = TRUE;
  457.       ll = win->file_info->line_list_end;
  458.       if (ll->prev != NULL)
  459.          *rcol = ll->prev->len;
  460.       else
  461.         *rcol = 0;
  462.       *rline = win->file_info->length;
  463.       ll = regx_search_backward( ll->prev, rline, rcol );
  464.  
  465.       if (ll == win->ll  &&  *rcol <= win->rcol)
  466.          ll = NULL;
  467.  
  468.       if (win->ll->prev != NULL)
  469.          win->ll->prev->len = end;
  470.    }
  471.    flush_keyboard( );
  472.  
  473.    if (ll != NULL)
  474.       bin_offset_adjust( win, *rline );
  475.    return( ll );
  476. }
  477.  
  478.  
  479. /*
  480.  * Name:    regx_search_backward
  481.  * Purpose: search backward for pattern using regular expression
  482.  * Date:    June 5, 1993
  483.  * Passed:  ll:     pointer to current node in linked list
  484.  *          rline:  pointer to real line counter
  485.  *          col:    column in ll->line to begin search
  486.  * Returns: position in file if found or NULL if not found
  487.  * Notes:   run the nfa machine on each character in each line
  488.  */
  489. line_list_ptr regx_search_backward( line_list_ptr ll, long *rline, int *col )
  490. {
  491.    if (ll == NULL)
  492.       return( NULL );
  493.    if (ll->len == EOF)
  494.       return( NULL );
  495.    else {
  496.       nfa_pointer = &nfa;
  497.       stacked_node_count = regx.node_count;
  498.  
  499.       search_string = ll->line;
  500.       search_len = ll->len;
  501.       search_col = *col;
  502.       reset_count = stacked_node_count * sizeof(int);
  503.       while (!g_status.control_break) {
  504.          for (; search_col >= 0; search_col--) {
  505.             if (nfa_match( ) != ERROR) {
  506.                *col = search_col;
  507.                return( ll );
  508.             }
  509.          }
  510.          --*rline;
  511.          ll = ll->prev;
  512.          if (ll == NULL)
  513.             return( NULL );
  514.          if (ll->len == EOF)
  515.             return( NULL );
  516.          search_string = ll->line;
  517.          search_col = search_len = ll->len;
  518.       }
  519.       return( NULL );
  520.    }
  521. }
  522.  
  523.  
  524. /******************************  NFA Recognizer  *********************/
  525.  
  526.  
  527. /*
  528.  * Name:    nfa_match
  529.  * Purpose: try to recognize a pattern
  530.  * Date:    June 5, 1993
  531.  * Passed:  none, but modifies local global nfa recognizer.
  532.  * Returns: length of recognized pattern if found or ERROR if not found.
  533.  */
  534. int  nfa_match( void )
  535. {
  536. register int c;
  537. int  state;
  538. int  j;
  539. int  n1;
  540. int  rc;
  541.  
  542.    j = search_col;
  543.    c  =  j < search_len  ?  search_string[j]  :  EOF;
  544.    state = nfa_pointer->next1[0];
  545.    dq_head = 0;
  546.    dq_tail = 0;
  547.    memset( queued_states, 0, reset_count );
  548.    put_dq( SCAN );
  549.  
  550.    while (state) {
  551.       if (state == SCAN) {
  552.          memset( queued_states, 0, reset_count );
  553.          j++;
  554.          put_dq( SCAN );
  555.          c  =  j < search_len  ?  search_string[j]  :  EOF;
  556.       } else if (nfa_pointer->node_type[state] == NNODE) {
  557.          n1 = nfa_pointer->next1[state];
  558.          rc = OK;
  559.          switch (nfa_pointer->term_type[state]) {
  560.             case STRAIGHT_ASCII :
  561.                if (nfa_pointer->c[state] == c)
  562.                   rc = put_dq( n1 );
  563.                break;
  564.             case IGNORE_ASCII   :
  565.                if (nfa_pointer->c[state] == tolower( c ))
  566.                   rc = put_dq( n1 );
  567.                break;
  568.             case WILD           :
  569.                if (j < search_len)
  570.                   rc = put_dq( n1 );
  571.                break;
  572.             case BOL            :
  573.                if (j == 0) {
  574.                   rc = put_dq( n1 );
  575.                   if (deque[dq_tail] == SCAN)
  576.                      --j;
  577.                }
  578.                break;
  579.             case EOL            :
  580.                if (j == search_len) {
  581.                   rc = put_dq( n1 );
  582.                   if (deque[dq_tail] == SCAN)
  583.                      --j;
  584.                }
  585.                break;
  586.             case CLASS          :
  587.                if (c != EOF  &&  nfa_pointer->class[state][c/8] & bit[c%8])
  588.                   rc = put_dq( n1 );
  589.                break;
  590.             case NOTCLASS       :
  591.                if (c != EOF  &&  !(nfa_pointer->class[state][c/8] & bit[c%8]))
  592.                   rc = put_dq( n1 );
  593.                break;
  594.             case WHITESPACE     :
  595.                if (c == ' '  ||  c == '\t')
  596.                   rc = put_dq( n1 );
  597.                break;
  598.             case ALPHA          :
  599.                if (c != EOF  &&  isalpha( c ))
  600.                   rc = put_dq( n1 );
  601.                break;
  602.             case UPPER          :
  603.                if (c != EOF  &&  isupper( c ))
  604.                   rc = put_dq( n1 );
  605.                break;
  606.             case LOWER          :
  607.                if (c != EOF  &&  islower( c ))
  608.                   rc = put_dq( n1 );
  609.                break;
  610.             case ALPHANUM       :
  611.                if (c != EOF  &&  isalnum( c ))
  612.                   rc = put_dq( n1 );
  613.                break;
  614.             case DECIMAL        :
  615.                if (c != EOF  &&  isdigit( c ))
  616.                   rc = put_dq( n1 );
  617.                break;
  618.             case HEX            :
  619.                if (c != EOF  &&  isxdigit( c ))
  620.                   rc = put_dq( n1 );
  621.                break;
  622.             default             :
  623.                assert( FALSE );
  624.                break;
  625.          }
  626.          if (rc == ERROR)
  627.             return( 0 );
  628.       } else {
  629.          assert( nfa_pointer->node_type[state] == CNODE );
  630.  
  631.          n1 = nfa_pointer->next1[state];
  632.          if (push_dq( n1 ) == ERROR)
  633.             return( 0 );
  634.  
  635.          if (n1 != nfa_pointer->next2[state])
  636.             if (push_dq( nfa_pointer->next2[state] ) == ERROR)
  637.                return( 0 );
  638.       }
  639.       if (dequeempty( )  ||  j > search_len)
  640.          return( ERROR );
  641.       state = pop_dq( );
  642.    }
  643.    return( j - search_col );
  644. }
  645.  
  646.  
  647. /*
  648.  * Name:    put_dq
  649.  * Purpose: queue future states
  650.  * Date:    June 5, 1993
  651.  * Passed:  v:  state to queue
  652.  * Returns: none, but modifies local global deque variables.  future
  653.  *           states are queued in the head.
  654.  * Notes:   do not add any duplicate states to the head of the deque.
  655.  */
  656. int  put_dq( int v )
  657. {
  658.    if (queued_states[v+1] == 0) {
  659.       ++queued_states[v+1];
  660.       deque[dq_head] = v;
  661.       dq_head--;
  662.       if (dq_head < 0)
  663.          dq_head = REGX_SIZE - 1;
  664.       if (dq_tail == dq_head) {
  665.          nfa_status = ERROR;
  666.          show_search_message( NFA_GAVE_UP, g_display.diag_color );
  667.          return( ERROR );
  668.       }
  669.    }
  670.    return( OK );
  671. }
  672.  
  673.  
  674. /*
  675.  * Name:    push_dq
  676.  * Purpose: push state on deque
  677.  * Date:    June 5, 1993
  678.  * Passed:  v:  state to push
  679.  * Returns: whether stack is OK or if stack overflowed - ERROR.  present
  680.  *           states are stacked.
  681.  */
  682. int  push_dq( int v )
  683. {
  684.    ++dq_tail;
  685.    if (dq_tail == dq_head) {
  686.       nfa_status = ERROR;
  687.       show_search_message( NFA_GAVE_UP, g_display.diag_color );
  688.       return( ERROR );
  689.    } else {
  690.       if (dq_tail > REGX_SIZE - 1)
  691.          dq_tail = 0;
  692.       deque[dq_tail] = v;
  693.       return( OK );
  694.    }
  695. }
  696.  
  697.  
  698. /*
  699.  * Name:    pop_dq
  700.  * Purpose: pop next state on dq
  701.  * Date:    June 5, 1993
  702.  * Passed:  none, but looks at local global nfa recognizer
  703.  * Returns: state on top of deque and decrements stack pointer
  704.  */
  705. int  pop_dq( void )
  706. {
  707. register int v;
  708.  
  709.    v = deque[dq_tail];
  710.    dq_tail--;
  711.    if (dq_tail < 0)
  712.       dq_tail = REGX_SIZE - 1;
  713.    return( v );
  714. }
  715.  
  716.  
  717. /*
  718.  * Name:    dequeempty
  719.  * Purpose: any room on dq?
  720.  * Date:    June 5, 1993
  721.  * Passed:  none, but looks at local global nfa recognizer
  722.  * Returns: boolean, TRUE if empty.
  723.  * Notes:   the deque is a circular array where future states are
  724.  *           queued in the head and present states are pushed in the tail.
  725.  */
  726. int  dequeempty( void )
  727. {
  728.    if (dq_tail > dq_head)
  729.       return( dq_tail - dq_head == 1 );
  730.    else
  731.       return( dq_tail + REGX_SIZE - dq_head == 1 );
  732. }
  733.  
  734.  
  735. /***************************  NFA Compiler  **************************/
  736.  
  737.  
  738. /*
  739.  * Name:    build_nfa
  740.  * Purpose: initialize nfa and call the compiler
  741.  * Date:    June 5, 1993
  742.  * Passed:  none, but looks at local global pattern.
  743.  * Returns: whether or not an ERROR occured
  744.  * Notes:   sets up the initial variables for the compiler.  builds
  745.  *          initial and acceptor states for the nfa after compiler finishes.
  746.  */
  747. int  build_nfa( void )
  748. {
  749.    regx_rc = OK;
  750.  
  751.    init_nfa( );
  752.    lookahead = 0;
  753.    reg_len   = strlen( (char *)regx.pattern );
  754.    parser_state = 1;
  755.  
  756.    nfa.next1[0] = expression( );
  757.    if (regx_rc == OK) {
  758.       emit_cnode( 0, START, nfa.next1[0], nfa.next1[0] );
  759.       emit_cnode( parser_state, ACCEPT, 0, 0 );
  760.       regx.node_count = parser_state + 2;
  761.    }
  762.  
  763.    if (g_status.command == DefineRegXGrep) {
  764.       memcpy( &sas_nfa, &nfa, sizeof(NFA_TYPE) );
  765.       memcpy( &sas_regx, ®x, sizeof(REGX_INFO) );
  766.    }
  767.    return( regx_rc );
  768. }
  769.  
  770.  
  771. /*
  772.  * Name:    expression
  773.  * Purpose: break reg ex into terms and expressions
  774.  * Date:    June 5, 1993
  775.  * Passed:  none, but looks at local global pattern.
  776.  * Returns: none
  777.  * Notes:   because recursion can go fairly deep, almost all variables
  778.  *          were made local global.  no need to save most of this stuff
  779.  *          on the stack.
  780.  */
  781. int  expression( void )
  782. {
  783. int t1;
  784. int t2;
  785. int r;
  786.  
  787.    t1 = term( );
  788.    r = t1;
  789.    if (regx.pattern[lookahead] == '|') {
  790.       lookahead++;
  791.       parser_state++;
  792.       r = t2 = parser_state;
  793.       parser_state++;
  794.       emit_cnode( t2, OR_NODE, expression( ), t1 );
  795.       emit_cnode( t2-1, JUXTA, parser_state, parser_state );
  796.  
  797.       /*
  798.        * the OR_NODE seems to need a path from the previous node
  799.        */
  800.       if (nfa.node_type[t1] == CNODE)
  801.          t1 = min( nfa.next1[t1], nfa.next2[t1] );
  802.       nfa.next1[t1-1] = t2;
  803.       if (nfa.node_type[t1-1] == NNODE)
  804.          nfa.next2[t1-1] = t2;
  805.    }
  806.    return( r );
  807. }
  808.  
  809.  
  810. /*
  811.  * Name:    term
  812.  * Purpose: break reg ex into factors and terms
  813.  * Date:    June 5, 1993
  814.  * Passed:  none, but looks at local global pattern.
  815.  * Returns: none
  816.  */
  817. int  term( void )
  818. {
  819. int r;
  820.  
  821.    r = factor( );
  822.    if (regx.pattern[lookahead] == '('  ||  letter( regx.pattern[lookahead] ))
  823.       term( );
  824. /*
  825.    else if (regx.pattern[lookahead]  ==  ')')
  826.       regx_error( reg3 );
  827. */
  828.    else if (Kleene_star( regx.pattern[lookahead] ))
  829.       regx_error( reg11 );
  830.    return( r );
  831. }
  832.  
  833.  
  834. /*
  835.  * Name:    factor
  836.  * Purpose: add NNODEs and CNODEs to local global nfa
  837.  * Date:    June 5, 1993
  838.  * Passed:  none
  839.  * Returns: none, but modifies local global nfa.
  840.  * Notes:   this function does most of the compiling.  it recognizes all
  841.  *          NNODEs, predefined macros, escape characters, and operators.
  842.  */
  843. int  factor( void )
  844. {
  845. int t1;
  846. int t2;
  847. int r;
  848. int c;
  849. int paren;
  850.  
  851.    t1 = parser_state;
  852.    c = regx.pattern[lookahead];
  853.    if (c == '(') {
  854.       lookahead++;
  855.       t2 = expression( );
  856.       if (regx.pattern[lookahead] == ')') {
  857.          lookahead++;
  858.          paren = TRUE;
  859.       } else
  860.  
  861.          /*
  862.           * unmatched open parens
  863.           */
  864.          regx_error( reg2 );
  865.    } else if (letter( c )) {
  866.       paren = FALSE;
  867.       switch (c) {
  868.          case ']' :
  869.  
  870.             /*
  871.              * unmatched close bracket
  872.              */
  873.             regx_error( reg9 );
  874.             break;
  875.          case '.' :
  876.             ttype = WILD;
  877.             break;
  878.          case ',' :
  879.             ttype = WHITESPACE;
  880.             break;
  881.          case '^' :
  882.             ttype = BOL;
  883.             break;
  884.          case '$' :
  885.             ttype = EOL;
  886.             break;
  887.          case '\\' :
  888.             ++lookahead;
  889.             ttype =  mode.search_case == IGNORE ? IGNORE_ASCII : STRAIGHT_ASCII;
  890.             if (lookahead != '\0') {
  891.                if (regx.pattern[lookahead] != ':')
  892.                   c = escape_char( regx.pattern[lookahead] );
  893.  
  894.                /*
  895.                 * predefined unix-like macros.
  896.                 */
  897.                else {
  898.                   c = regx.pattern[lookahead+1];
  899.                   if (c != '\0') {
  900.                      switch (c) {
  901.                         case 'a' :
  902.                            ++lookahead;
  903.                            ttype = ALPHANUM;
  904.                            break;
  905.                         case 'b' :
  906.                            ++lookahead;
  907.                            ttype = WHITESPACE;
  908.                            break;
  909.                         case 'c' :
  910.                            ++lookahead;
  911.                            ttype = ALPHA;
  912.                            break;
  913.                         case 'd' :
  914.                            ++lookahead;
  915.                            ttype = DECIMAL;
  916.                            break;
  917.                         case 'h' :
  918.                            ++lookahead;
  919.                            ttype = HEX;
  920.                            break;
  921.                         case 'l' :
  922.                            ++lookahead;
  923.                            ttype = LOWER;
  924.                            break;
  925.                         case 'u' :
  926.                            ++lookahead;
  927.                            ttype = UPPER;
  928.                            break;
  929.                         default :
  930.                            c = escape_char( regx.pattern[lookahead] );
  931.                            break;
  932.                      }
  933.                   } else
  934.                      c = escape_char( regx.pattern[lookahead] );
  935.                }
  936.             } else
  937.                regx_error( reg4 );
  938.             break;
  939.          case '[' :
  940.             memset( class_bits, 0, sizeof(char) * 32 );
  941.             ++lookahead;
  942.             if (lookahead != '\0') {
  943.                c = regx.pattern[lookahead];
  944.                if (c == '^') {
  945.                   ++lookahead;
  946.                   ttype = NOTCLASS;
  947.                } else
  948.                   ttype = CLASS;
  949.  
  950.                c1 = regx.pattern[lookahead];
  951.                do {
  952.                   class_bits[c1/8]  |=  bit[c1%8];
  953.                   if (c1 != '\0')
  954.                      ++lookahead;
  955.                   if (regx.pattern[lookahead] == '-') {
  956.                      ++lookahead;
  957.                      c2 = regx.pattern[lookahead];
  958.                      if (c2 != '\0') {
  959.  
  960.                         /*
  961.                          * just in case the hi for the range is given first,
  962.                          *  switch c1 and c2,  e.g. [9-0].
  963.                          */
  964.                         if (c2 < c1) {
  965.                            c  = c2;
  966.                            c2 = c1;
  967.                            c1 = c;
  968.                         }
  969.  
  970.                         for (c=c1; c <= c2; c++)
  971.                            class_bits[c/8] |= bit[c%8];
  972.  
  973.                         if (regx.pattern[lookahead] != '\0')
  974.                            ++lookahead;
  975.                      } else
  976.                         regx_error( reg10 );
  977.                   }
  978.                   c1 = regx.pattern[lookahead];
  979.                } while (c1  != '\0'  &&  c1 != ']');
  980.  
  981.                if (c1 == '\0')
  982.                   regx_error( reg5 );
  983.             } else
  984.                regx_error( reg6 );
  985.             break;
  986.          default :
  987.             if (mode.search_case == IGNORE) {
  988.                c = tolower( c );
  989.                ttype = IGNORE_ASCII;
  990.             } else
  991.                ttype = STRAIGHT_ASCII;
  992.       }
  993.       emit_nnode( parser_state, ttype, c, parser_state+1, parser_state+1 );
  994.       if (ttype == CLASS  ||  ttype == NOTCLASS) {
  995.          nfa.class[parser_state] = calloc( 32, sizeof(char) );
  996.          if (nfa.class[parser_state] != NULL)
  997.             memcpy( nfa.class[parser_state], class_bits, sizeof( char )*32 );
  998.          else
  999.             regx_error( reg7 );
  1000.       }
  1001.       t2 = parser_state;
  1002.       lookahead++;
  1003.       parser_state++;
  1004.    } else if (c == '\0')
  1005.       return( 0 );
  1006.    else {
  1007.       if (c == '*'  ||  c == '+'  ||  c == '?')
  1008.          regx_error( reg8 );
  1009.       else if (c  ==  ')')
  1010.          regx_error( reg3 );
  1011.       else
  1012.          regx_error( reg2 );
  1013.    }
  1014.  
  1015.    c = regx.pattern[lookahead];
  1016.    switch (c) {
  1017.       case '*' :
  1018.          emit_cnode( parser_state, CLOSURE, parser_state+1, t2 );
  1019.          r = parser_state;
  1020.          if (nfa.node_type[t1] == CNODE)
  1021.             t1 = min( nfa.next1[t1], nfa.next2[t1] );
  1022.          nfa.next1[t1-1] = parser_state;
  1023.          if (nfa.node_type[t1-1] == NNODE)
  1024.             nfa.next2[t1-1] = parser_state;
  1025.          lookahead++;
  1026.          parser_state++;
  1027.          paren = FALSE;
  1028.          break;
  1029.       case '+' :
  1030.          if (paren == TRUE) {
  1031.             emit_cnode( parser_state, JUXTA, parser_state+2, parser_state+2 );
  1032.             parser_state++;
  1033.          }
  1034.  
  1035.          emit_cnode( parser_state, JUXTA, t2, t2 );
  1036.          r = parser_state;
  1037.          parser_state++;
  1038.  
  1039.          if (paren == FALSE) {
  1040.             nfa.next1[t2] = parser_state;
  1041.             if (nfa.node_type[t2] == NNODE)
  1042.                nfa.next2[t2] = parser_state;
  1043.          }
  1044.  
  1045.          emit_cnode( parser_state, CLOSURE, parser_state+1, t2 );
  1046.          if (nfa.node_type[t1] == CNODE)
  1047.             t1 = min( nfa.next1[t1], nfa.next2[t1] );
  1048.          nfa.next1[t1-1] = r;
  1049.          if (nfa.node_type[t1-1] == NNODE)
  1050.             nfa.next2[t1-1] = r;
  1051.          parser_state++;
  1052.          lookahead++;
  1053.          paren = FALSE;
  1054.          break;
  1055.       case '?' :
  1056.          emit_cnode( parser_state, JUXTA, parser_state+2, parser_state+2 );
  1057.          parser_state++;
  1058.          r = parser_state;
  1059.          emit_cnode( parser_state, ZERO_OR_ONE, parser_state+1, t2 );
  1060.          if (nfa.node_type[t1] == CNODE)
  1061.             t1 = min( nfa.next1[t1], nfa.next2[t1] );
  1062.          nfa.next1[t1-1] = parser_state;
  1063.          if (nfa.node_type[t1-1] == NNODE)
  1064.             nfa.next2[t1-1] = parser_state;
  1065.          parser_state++;
  1066.          lookahead++;
  1067.          paren = FALSE;
  1068.          break;
  1069.       default  :
  1070.          r = t2;
  1071.          break;
  1072.    }
  1073.  
  1074.    /*
  1075.     * close parens seem to need a JUXTA node to gather all reg ex's
  1076.     *  to a common point.
  1077.     */
  1078.    if (paren) {
  1079.       emit_cnode( parser_state, JUXTA, parser_state+1, parser_state+1 );
  1080.       parser_state++;
  1081.    }
  1082.    return( r );
  1083. }
  1084.  
  1085.  
  1086. /*
  1087.  * Name:    escape_char
  1088.  * Purpose: recognize escape and C escape sequences
  1089.  * Date:    June 5, 1993
  1090.  * Passed:  let:  letter to escape
  1091.  * Returns: escaped letter
  1092.  */
  1093. int  escape_char( int let )
  1094. {
  1095.    switch (let) {
  1096.       case '0' :
  1097.          let = 0x00;
  1098.          break;
  1099.       case 'a' :
  1100.          let = 0x07;
  1101.          break;
  1102.       case 'b' :
  1103.          let = 0x08;
  1104.          break;
  1105.       case 'n' :
  1106.          let = 0x0a;
  1107.          break;
  1108.       case 'r' :
  1109.          let = 0x0d;
  1110.          break;
  1111.       case 't' :
  1112.          let = 0x09;
  1113.          break;
  1114.       default  :
  1115.          break;
  1116.    }
  1117.    return( let );
  1118. }
  1119.  
  1120.  
  1121. /*
  1122.  * Name:    emit_cnode
  1123.  * Purpose: add a null node to our pattern matching machine
  1124.  * Date:    June 5, 1993
  1125.  * Passed:  index:  current node in nfa
  1126.  *          ttype:  terminal type - CLOSURE, OR, ONEORMORE, etc...
  1127.  *          n1:     pointer to next state, path for lambda transitions
  1128.  *          n2:     pointer to other next state, usually a NNODE
  1129.  * Returns: none, but modifies local global nfa.
  1130.  */
  1131. void emit_cnode( int index, int ttype, int n1, int n2 )
  1132. {
  1133.    assert( index >= 0);
  1134.    assert( index < REGX_SIZE );
  1135.  
  1136.    nfa.node_type[index] = CNODE;
  1137.    nfa.term_type[index] = ttype;
  1138.    nfa.c[index] = 0;
  1139.    nfa.next1[index] = n1;
  1140.    nfa.next2[index] = n2;
  1141. }
  1142.  
  1143.  
  1144. /*
  1145.  * Name:    emit_nnode
  1146.  * Purpose: add a to our pattern matching machine
  1147.  * Date:    June 5, 1993
  1148.  * Passed:  index:  current node in nfa
  1149.  *          ttype:  terminal type - EOL, ASCII, etc...
  1150.  *          c:      letter this node recognizes
  1151.  *          n1:     pointer to next state
  1152.  *          n2:     pointer to other next state, which can be same as n1
  1153.  * Returns: none, but modifies local global nfa.
  1154.  */
  1155. void emit_nnode( int index, int ttype, int c, int n1, int n2 )
  1156. {
  1157.    assert( index >= 0);
  1158.    assert( index < REGX_SIZE );
  1159.  
  1160.    nfa.node_type[index] = NNODE;
  1161.    nfa.term_type[index] = ttype;
  1162.    nfa.c[index] = c;
  1163.    nfa.next1[index] = n1;
  1164.    nfa.next2[index] = n2;
  1165. }
  1166.  
  1167.  
  1168. /*
  1169.  * Name:    init_nfa
  1170.  * Purpose: set local global nfa to NULL state
  1171.  * Date:    June 5, 1993
  1172.  * Passed:  none
  1173.  */
  1174. void init_nfa( void )
  1175. {
  1176. int i;
  1177.  
  1178.    for (i=0; i < REGX_SIZE; i++) {
  1179.       nfa.node_type[i] = NNODE;
  1180.       nfa.term_type[i] = 0;
  1181.       nfa.c[i] = 0;
  1182.       nfa.next1[i] = 0;
  1183.       nfa.next2[i] = 0;
  1184.       if (nfa.class[i] != NULL)
  1185.          free( nfa.class[i] );
  1186.       nfa.class[i] = NULL;
  1187.    }
  1188. }
  1189.  
  1190.  
  1191. /*
  1192.  * Name:    regx_error
  1193.  * Purpose: display reg ex error message and set reg ex error code
  1194.  * Date:    June 5, 1993
  1195.  * Passed:  line:  line to display error
  1196.  * Returns: none, but sets reg ex return code to error.
  1197.  */
  1198. void regx_error( char *line )
  1199. {
  1200.    error( WARNING, regx_error_line, line );
  1201.    regx_rc = ERROR;
  1202. }
  1203.  
  1204.  
  1205. /*
  1206.  * Name:    separator
  1207.  * Purpose: determine if character is a reg ex separator
  1208.  * Date:    June 5, 1993
  1209.  * Passed:  let:  letter to look at
  1210.  * Returns: whether or not 'let' is a separator
  1211.  */
  1212. int  separator( int let )
  1213. {
  1214.    return( let == 0  ||  let == ')'  ||  let == '|' );
  1215. }
  1216.  
  1217.  
  1218. /*
  1219.  * Name:    Kleene_star
  1220.  * Purpose: determine if character is a reg ex operator
  1221.  * Date:    June 5, 1993
  1222.  * Passed:  let:  letter to look at
  1223.  * Returns: whether or not 'let' is a letter
  1224.  */
  1225. int  Kleene_star( int let )
  1226. {
  1227.    return( let == '*'  ||  let == '+'  ||  let == '?' );
  1228. }
  1229.  
  1230.  
  1231. /*
  1232.  * Name:    letter
  1233.  * Purpose: determine if character is a recognized reg ex character
  1234.  * Date:    June 5, 1993
  1235.  * Passed:  let:  letter to look at
  1236.  * Returns: whether or not 'let' is a letter.
  1237.  */
  1238. int  letter( int let )
  1239. {
  1240.    return( !separator( let )  &&  !Kleene_star( let ) );
  1241. }
  1242.